1. Field of the Invention
The present invention relates to a technique for determining a method for interpolating a pixel.
2. Description of the Related Art
In an interlace/progressive (IP) conversion for converting an image of an interlace format to a progressive format and a process for enlarging a still picture or a moving picture, it is necessary to interpolate a pixel not existing in an input original image. Where a pixel to be interpolated is defined as “target pixel”, a selection of a plurality of pixels for one target pixel and a calculation of the pixel value of the target pixel based on the respective pixel values of the plurality of pixels usually interpolate the target pixel.
For interpolating a pixel, there are various methods which can be categorized by a first viewpoint of how to select the plurality of pixels and a second viewpoint of how to calculate the pixel value of the target pixel from the pixel value of the selected plurality of pixels. The following outlines the techniques related to the methods for interpolating a pixel particularly in the IP conversion from the first viewpoint.
Before describing the IP conversion, an interlace method and a progressive method are first described. A scanning methods for displaying a moving picture in a display include an interlace method and a progressive method. The interlace method is a method for repeatedly alternating between a scan of only the odd numbered scan line and that of only the even numbered scan line, and the method is used for an analog input television and such. Meanwhile, the progressive method is a method for scanning all scan lines, and the method is used for a cathode ray tube (CRT) of a personal computer (PC) and the like. Further, the names “interlace” and “progressive” are also used as the names of the formats of the respective images generated so as to be displayed appropriately depending on which of the above described scan method is used.
As an example, in the case of a frame rate being thirty (30) frames per second (fps), that is, the number of frames per second is thirty, a progressive image is a moving picture consisting of thirty frames per second. In contrast, an interlace image is constituted by sixty field images per second in this case because two fields correspond to one frame. One of the two fields corresponding to one frame is called an “odd field”, and the other is called an “even field”. The field image of the odd field includes only the data of pixels on the odd numbered lines, and that of the even field includes only the data of pixels on the even numbered lines. Note that one scan line in a display corresponds to one line in the image. In the case of the frame rate being 30 fps, the n-th line and (n+1)-th line within one frame image correspond to the same clock time for a progressive image, while there is a shift of 1/60 seconds between the n-th line and (n+1)-th line for an interlace image.
In the following description, a line in which the data of pixels exist is called a “real line” and an empty line in which the data of pixels do not exist is called an “interpolation line”. That is, the odd numbered line is a real line and the even numbered line is an interpolation line in the odd field, while they are vice versa in the even field. Also, a pixel on the real line is hereinafter called a “real pixel”.
The IP conversion is a process for receiving an interlace image as input, converting it into a progressive image, and outputting the progressive image. Where the frame rate of the input interlace image is f, there are 2f field images per second. The IP conversion is a process for interpolating a pixel on an interpolation line. As a result, an image in which the data of pixels on all the lines are included is obtained for each field image. That is, a progressive image whose frame rate is 2f is obtained.
In order to obtain a progressive image with high image quality by using an IP conversion, it is necessary to detect the motion and the direction of edges in the neighborhood of a target pixel, and to interpolate the target pixel appropriately. One method for achieving such an interpolation is a motion adaptive IP conversion.
The motion adaptive IP conversion carries out an intra-field interpolation for interpolating a target pixel on the basis of the pixel values of pixels on lines existing above and below the target pixel within the same field image if a motion is detected. If a stationary state is detected on the other hand, it carries out an inter-field interpolation for interpolating a target pixel on the basis of the pixel values of pixels existing at the same position as the target pixel in the precedent and subsequent field images of the field containing the target pixel. That is, in the above-mentioned first viewpoint, the characteristic of the motion adaptive IP conversion lies in selecting pixels in the same field if a motion is detected and selecting pixels in the precedent and subsequent fields if a motion is not detected.
The motion adaptive IP conversion has an advantage, that is, a smaller process volume, while it has a disadvantage, that is, inferior accuracy in interpolation to a method, such as a motion compensation IP conversion, for interpolating by calculating a motion vector for each pixel. Due to this reason, various methods of motion adaptive IP conversions have been proposed for the purpose of improving the accuracy.
As an example, the simplest method of a motion adaptive IP conversion is the method shown in FIG. 1. In this method, the pixels positioned right above and right below of the target pixel to be interpolated are used for an intra-field interpolation if a motion is detected. In the following description, the horizontal direction is represented by the x coordinate, the vertical direction is represented by the y coordinate and each pixel is represented by a square. The x coordinate represents its value being “0” at the left edge of an image, with the value increasing as a point moves rightward, and the y coordinate represents its value being “0” at the top edge of the image, with the value increasing as a point moves downward. Referring to FIG. 1, the input interlace image includes only the lines of y=0, 2, 4 and 6, with the respective lines of y=1, 3 and 5 being interpolation lines. Accordingly, if the interlace image includes a diagonal edge as shown on the left side of FIG. 1, a post-interpolation progressive image results in generating a stepwise jagged pattern called a “jaggy” as shown on the right side of FIG. 1.
Where the position of a pixel is expressed by a pair of coordinates (x, y), the pixel at the position expressed by, for example, the coordinates (2, 3) (simply noted as “pixel of (2, 3)” or the like hereinafter) is interpolated on the basis of the white pixel existing at the right upper position (2, 2) and the black pixel existing at the right lower position (2, 4). As an example, the average value of the pixel values of the two pixels is assigned as the pixel value of the target pixel so that it is interpolated as gray. The pixel of (3, 3) is also interpolated as gray in the similar manner. As a result, a jaggy is generated in the progressive image. The other parts of the diagonal edge, that is, the parts (0, 5), (1, 5), (4, 1) and (5, 1) are also similar.
If, however, the respective pixels of the (0, 5), (2, 3) and (4, 1) were interpolated as white and the respective pixels of the (1, 5), (3, 3) and (5, 1) were interpolated as black, a progressive image including a smooth diagonal edge without a jaggy would have been obtained. That is, the method simply using the pixels at the right upper and lower positions as shown in FIG. 1 may not be able to obtain a high image quality as an interpolation result.
Accordingly, the methods noted in reference patent documents 1 through 4 have been proposed. Note that the following description has changed a part of terminologies used in the individual reference documents for an easy understanding by unifying the terminologies.
FIG. 2 is a diagram describing the interpolation method noted in the reference patent document 1. When determining a pixel existing in which direction is to be used for interpolating a target pixel T, this method utilizes also a line other than the two adjacent lines (that is, the upper adjacent line and the lower adjacent line) adjacent to the line on which the target pixel T is positioned.
Referring to FIG. 2, the target pixel T is positioned at (3, 3). With the target pixel T positioned at the center, a correlation between the pixel on the y=2 line and that on the y=4 line is calculated for several directions. For example, the vertical direction corresponds to the set of the white pixel at (3, 2) and black pixel at (3, 4), indicating a weak correlation. In contrast, the direction connecting the back pixel at (5, 2) and that at (1, 4), where the direction is shown as the diagonal line rising from left to right (noted as “uphill gradient” hereinafter) indicated by an arrow, is detected as the strongest correlation. In a similar manner, the correlation in the vertical direction indicated by another arrow is detected as a strong correlation for reference pixel R1 positioned at (3, 1), which is right above the target pixel T by two lines, and the correlation in the diagonal line rising from right to left (noted as “downhill gradient” hereinafter) indicated by another arrow is detected as a strong correlation for reference pixel R2 positioned at (3, 5), which is right below the target pixel T by two lines.
The direction of the downhill gradient detected for the reference pixel R2 is a direction opposite to the direction of the uphill gradient. In the reference patent document 1, if such an opposite direction is detected, the direction of interpolation of the target pixel T is determined to be the vertical direction, in lieu of a diagonal direction, in consideration of the consistency with a direction indicating a strong correlation in the neighborhood of the target pixel T. Note that “the interpolation direction is the vertical direction” means that the target pixel T is interpolated on the basis of pixel values of two pixels existing at (3, 2) and (3, 4) which correspond to each other in the vertical direction. Similarly, if the directions detected respectively for the reference pixel R1 and target pixel T are opposite to each other, the interpolation direction of the target pixel T is determined to be the vertical direction.
FIG. 3 is a diagram describing the interpolation method noted in the reference patent document 2. Also in the method noted therein, the pixel positioned right above the target pixel T by two lines is utilized as reference pixel R. In this method, a correlation in the uphill gradient direction is calculated by adding the correlation value in the uphill gradient direction related to the target pixel T and the correlation value in the uphill gradient direction related to the reference pixel R. This is similar for the downhill gradient direction. If the direction having a stronger correlation in the uphill and downhill gradient directions shows a stronger correlation than a predetermined threshold value, the direction is selected as the interpolation direction.
In the example of FIG. 3, the correlation of the uphill gradient direction is weak for the target pixel T and strong for the reference pixel R. Therefore, the correlation in the uphill gradation direction is judged to be relatively weak as a whole based on the sum of the two correlation values. Meanwhile, the correlation in the downhill gradient direction is strong for the target pixel T and weak for the reference pixel R. Therefore, the correlation in the downhill gradient direction is also judged to be relatively weak as a whole based on the sum of the two correlation values. As a result, the vertical direction, which is the direction indicating the strong correlation for both the target pixel T and reference pixel R, is selected as the interpolation direction for the target pixel T.
FIG. 4 is a diagram describing the interpolation method noted in the reference patent document 3. This method determines an interpolation direction on the basis of the correlation between a pair of regions including plural pixels, instead of the correlation between pixels. As an example, a region constituted by nine pixels (i.e., 3×3=9) is utilized, as shown in FIG. 4.
In the center pixel region A with the target pixel T at the center, three pixels in the top line and three pixels in the bottom line are real pixels. Likewise in the surrounding pixel region B1 existing diagonally (namely, in the downhill gradient direction) above the center pixel region A and in the surrounding pixel region B2 existing diagonally (namely, in the downhill gradient direction) below the center pixel region A, the respective top and bottom lines are real lines and the respective center lines are interpolation lines. FIG. 4 delineates only the two surrounding pixel regions B1 and B2 which are positioned symmetrically with the center pixel region A being at the center; there are actually, for example, ten surrounding pixel regions B1 through B10 in a manner to surround the center pixel region A.
For each region, the weighted sum of the pixel values of the pixels included in the region is calculated. Then, for each j, the correlation between the center pixel region A and the surrounding pixel region Bj (where j=1, 2, 3 and so on) is calculated on the basis of the respective weighed sums. As an example, the correlation in the downhill gradient direction connecting the surrounding pixel regions B1 and B2 is the sum of the correlation value between the center pixel region A and surrounding pixel region B1 and the correlation value between the center pixel region A and surrounding pixel region B2.
As such, the correlation values are calculated for the respective directions and the direction having the strongest correlation is selected as the interpolation direction. FIG. 4 shows the case in which the downhill gradient direction connecting the surrounding pixel regions B1 and B2 is selected as the interpolation direction. Then, two pixels existing in the interpolation direction starting from the target pixel T on the lines above and below the target pixel T are selected so that the target pixel T is interpolated on the basis of the pixel values of these two pixels.
FIG. 5 is a diagram describing the interpolation method noted in the reference patent document 4. The assumption for example is that the correlation between the pixel at the upper right of the target pixel T and the pixel at the lower left thereof is strong and that the direction of the uphill gradient shown in the drawing (1) is detected as the direction having the strongest correlation for the target pixel T. In contrast, for the reference pixels R1 and R2, which are adjacent to the target pixel T on the right and left, the assumption is that the direction of the downhill gradient is detected as the direction having the strongest correlation.
As such, if the direction detected as the direction having the strongest correlation for the target pixel T is reverse, in terms of left and right, to the direction detected for the reference pixel R1 or R2, then it may be an erroneous detection. In such a case, the interpolation direction for the target pixel T is modified to the vertical direction as shown in the drawing (2) for preventing the interpolation in a wrong diagonal direction.
In the case shown in the drawing (3), however, the modification to the vertical direction is inappropriate. Suppose that a straight line L is defined as a line having an uphill gradient direction detected in the drawing (1) for the target pixel T and going through the target pixel T. Also suppose that reference pixels R3 and R4 are defined as respective pixels at intersection points where respective interpolation lines, which are positioned above and below an interpolation line on which the target pixel T is positioned, and the straight line L cross. If the same direction as the inclination of the straight line L is detected as the direction having the strongest correlation for the reference pixels R3 or R4, the interpolation direction for the target pixel T is re-modified to the original uphill gradient direction as shown in the drawing (4).
The methods described above are different in various ways in terms of in which direction starting from the target pixel the pixels are to be selected as an interpolation-use pixel; they are, however, the same in terms of considering the pixels surrounding the target pixel. The problem is that there is a kind of image in which an interpolation direction is apt to be detected wrongly even with such a consideration of the pixels surrounding a target pixel.
FIG. 6 exemplifies such an image in which a narrow diagonal line such as a string exists in a flat background. In FIG. 6, a black narrow line exists in an uphill gradient direction in a white background. As an example, the pixel positioned at the position (3, 3) on the interpolation line is on the black line and therefore it is desired to be interpolated as black.
Where the pixel of (3, 3) is defined as the target pixel, black pixels exist at both (4, 2) and (2, 4) and therefore the correlation is strong in an uphill gradient direction, that is, in the same direction as the black line. Meanwhile, this black line is so fine that the correlation between pixels existing at (2, 2) and (4, 4), both of the pixels belonging to the white background, is also strong. That is, the correlations in both the uphill gradient direction and downhill gradient direction are about the same for the target pixel at (3, 3). This fact is similar for other pixels to be interpolated as black on interpolation lines.
Incidentally, there are many cases where a general image includes some pixels with a little different pixel values while the pixels look like the same color. As a result of being such a slight difference in pixel values, the detection may possibly be such that the correlation is the strongest in the uphill gradient direction at, for example, (3, 3) and that the correlation is the strongest in the downhill gradient direction at (5, 1). This causes the black line to be correctly interpolated at (3, 3), while it is interpolated as the color of background (namely, white) at (5, 1), resulting in the black line being interrupted thereat.
That is, the use, for interpolation, of a pixel existing in a direction having the strongest correlation for a target pixel may result in erring the interpolation direction, thus generating an unclean image containing a broken line as shown in FIG. 6. Further, even with the use of a method, such as the reference patent documents 1 through 4, considering the surrounding pixels, the interpolation direction may be erroneously selected because the direction detected as a direction having the strongest for the target pixel is opposite to the direction detected as a direction having the strongest correlation for the surrounding pixel in an image as shown in FIG. 6.
Patent document 1: Laid-Open Japanese Patent Application Publication No. 2003-230109
Patent document 2: WO 2004/017634
Patent document 3: Laid-Open Japanese Patent Application Publication No. 2005-341337
Patent document 4: Laid-Open Japanese Patent Application Publication No. 2003-143555
As noted above, several methods have been proposed for the motion adaptive IP conversion, there is, however, a room for improvement in the selection of pixels used for interpolation. Further, the determination method for an interpolation method, that is, the determination method for determining how to interpolate a pixel and determining which pixels to be used for interpolation, is applicable to a general interpolation of a pixel in lieu of being limited to the motion adaptive IP conversion.